import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:大根堆 小根堆
 * User: Admin
 * Date: 2022-05-23
 * Time: 17:39
 */
public class TestHeap {
    public int elem[];
    public int UsedSize;

    public TestHeap(){
        this.elem = new int[10];
    }

    public void createHeap(int[] array) {
        for(int i = 0; i < array.length;i++) {
            elem[i] = array[i];
            UsedSize++;
        }

        for (int i = (UsedSize-1-1)/2 ; i >=0  ; i--) {
            shiftDown(i);
        }
    }

    public void shiftDown(int root) {
        int child = root*2+1;

        while(child < UsedSize) {

            if (child + 1 < UsedSize && elem[child+1] > elem[child]) {
                child++;
            }

            if(elem[child] > elem[root]) {
                int tmp = elem[child];
                elem[child] = elem[root];
                elem[root] = tmp;

                root = child;
                child = root*2+1;
            } else {
                break;
            }
        }
    }

    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }

        elem[UsedSize] = val;
        ShiftUp(UsedSize);
        UsedSize++;
    }
    private void ShiftUp(int cur) {
        int parent = (cur-1)/2;

        while(parent >= 0) {
         if (elem[cur] > elem[parent]) {
             int tmp = elem[cur];
             elem[cur] = elem[parent];
             elem[parent] = tmp;
             cur = parent;
             parent = (cur-1)/2;
         } else {
             break;
         }
     }
    }

    public boolean isFull() {
        return this.UsedSize == elem.length;
    }


    public void pollHeap() {
        if(empty()) {
            System.out.println("优先级队列为空");
            return;
        }

        elem[0] = elem[UsedSize-1];
        UsedSize--;
        shiftDown(0);
    }

    public boolean empty() {
        return UsedSize == 0;
    }

    public int peekHeap() {
        if(empty()) {
            System.out.println("优先级队列为空");
            return -1;
        }

        return elem[0];
    }
}
